The isomorphism problem: from lattices to graphs

T. Camus

We study the algorithmic complexity of the Lattices Isometry Problem (LIP), the aim of which is to decide whether two given lattices are isometric. We prove that a weakened version of this problem is reducible to the famous Graphs Isomorphism Problem (GIP). Used in combination with the recent quasi-polynomial resolution of GIP due to Babai [6], this reduction allows us to exhibit an algorithm that solves LIP in a time quasi-polynomial in the number of relatively short vectors in the lattices considered. 

Advanced Studies: Euro-Tbilisi Mathematical Journal, Special Issue (9 - 2021), pp. 81-104